/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-27 11:06:29
 * @LastEditors: lily
 * @LastEditTime: 2021-04-27 11:20:54
 */
/*
 * @lc app=leetcode.cn id=442 lang=javascript
 *
 * [442] 数组中重复的数据
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
//  思路：哈希表 同448
//  数字出现就加len标记，出现两次表示至少加了2len
//  再利用原数组作为哈希表降低空间复杂度

// 复杂度：O(n) O(1)

var findDuplicates = function (nums) {
    let res = [], len = nums.length
    for (let num of nums) {
        // 确定原来的值
        let n = (num - 1) % len + 1
        // 每出现一次增加len
        nums[n - 1] = nums[n - 1] + len
    }
    nums.forEach((num, i) => {
        // 找出加过两次len的数，返回下标
        if (num > 2 * len) {
            res.push(i + 1)
        }
    });
    return res
};
// @lc code=end

console.log(findDuplicates([4, 3, 2, 7, 8, 2, 3, 1]));